package com.lql.tree;

/**
 * 遍历二叉树（先序、中序、后序）
 */
public class ListBinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode heroNode1 = new HeroNode(2, "吴用");
        HeroNode heroNode2 = new HeroNode(3, "卢俊义");
        HeroNode heroNode3 = new HeroNode(4, "林冲");
        HeroNode heroNode4 = new HeroNode(5, "关胜");
        //建立联系
        root.setLeft(heroNode1);
        root.setRight(heroNode2);
        heroNode2.setLeft(heroNode4);
        heroNode2.setRight(heroNode3);

        //定义ListBinaryTree遍历
        ListBinaryTree listBinaryTree = new ListBinaryTree(root);
        listBinaryTree.preOrder();
        System.out.println("__________________");

        listBinaryTree.deleteNode(5);
        listBinaryTree.preOrder();
    }
}

class ListBinaryTree {
    //根节点
    private HeroNode root;

    public ListBinaryTree(HeroNode root) {
        this.root = root;
    }

    /**
     * 先序遍历
     */
    public void preOrder() {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("树为空！");
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder() {
        if (root != null) {
            root.midOrder();
        } else {
            System.out.println("树为空！");
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        if (root != null) {
            root.postOrder();
        } else {
            System.out.println("树为空！");
        }
    }

    /**
     * 先序查找
     *
     * @param no 要查找的员工id
     * @return 返回查找到的员工，否则返回null
     */
    public HeroNode preOrderSeek(int no) {
        if (root != null) {
            HeroNode heroNode = root.preOrderSeek(no);
            if (heroNode == null) {
                System.out.println("未找到id为" + no + "的员工");
                return null;
            }
            System.out.println("查找到的员工名称为" + heroNode.getName());
            return heroNode;
        } else {
            System.out.println("树为空！");
            return null;
        }
    }

    /**
     * 中序查找
     *
     * @param no 要查找的员工id
     * @return 返回查找到的员工，否则返回null
     */
    public HeroNode midOrderSeek(int no) {
        if (root != null) {
            HeroNode heroNode = root.midOrderSeek(no);
            if (heroNode == null) {
                System.out.println("未找到id为" + no + "的员工");
                return null;
            }
            System.out.println("查找到的员工名称为" + heroNode.getName());
            return heroNode;
        } else {
            System.out.println("树为空！");
            return null;
        }
    }

    /**
     * 后序查找
     *
     * @param no 要查找的员工id
     * @return 返回查找到的员工，否则返回null
     */
    public HeroNode postOrderSeek(int no) {
        if (root != null) {
            HeroNode heroNode = root.postOrderSeek(no);
            if (heroNode == null) {
                System.out.println("未找到id为" + no + "的员工");
                return null;
            }
            System.out.println("查找到的员工名称为" + heroNode.getName());
            return heroNode;
        } else {
            System.out.println("树为空！");
            return null;
        }
    }

    /**
     * 删除节点
     *
     * @param no 待删除编号
     */
    public void deleteNode(int no) {
        if (root != null) {
            if (root.getId() == no) {
                //根节点为待删除节点
                root = null;
                return;
            }
            root.deleteNode(no);
        } else {
            System.out.println("树为空，删除失败！");
        }
    }
}

class HeroNode {
    private int id;
    private String name;
    private HeroNode left;//左子树
    private HeroNode right;//右子树

    public HeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 先序遍历
     */
    public void preOrder() {
        //遍历当前节点
        System.out.println(this);
        if (this.left != null) {
            //左递归
            this.left.preOrder();
        }
        if (this.right != null) {
            //右递归
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder() {
        if (this.left != null) {
            //左递归
            this.left.midOrder();
        }
        //遍历当前节点
        System.out.println(this);
        if (this.right != null) {
            //右递归
            this.right.midOrder();
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        if (this.left != null) {
            //左递归
            this.left.postOrder();
        }
        if (this.right != null) {
            //右递归
            this.right.postOrder();
        }
        //遍历当前节点
        System.out.println(this);
    }

    /**
     * 先序查找
     *
     * @param no 要查找的员工id
     * @return 返回查找到的员工，否则返回null
     */
    public HeroNode preOrderSeek(int no) {
        //遍历当前节点
        if (no == this.id) {
            //找到直接返回
            return this;
        }
        HeroNode heroNode = null;
        if (this.left != null) {
            //左递归查找
            heroNode = this.left.preOrderSeek(no);
        }
        if (heroNode != null) {
            //在左子树上查找到
            return heroNode;
        }
        if (this.right != null) {
            //右递归
            heroNode = this.right.preOrderSeek(no);
        }
        return heroNode;
    }

    /**
     * 中序查找
     *
     * @param no 要查找的员工id
     * @return 返回查找到的员工，否则返回null
     */
    public HeroNode midOrderSeek(int no) {
        HeroNode heroNode = null;
        if (this.left != null) {
            //左递归查找
            heroNode = this.left.midOrderSeek(no);
        }
        //遍历当前节点
        if (no == this.id) {
            //找到直接返回
            return this;
        }
        if (heroNode != null) {
            //在左子树上查找到
            return heroNode;
        }
        if (this.right != null) {
            //右递归
            heroNode = this.right.midOrderSeek(no);
        }
        return heroNode;
    }

    /**
     * 后序查找
     *
     * @param no 要查找的员工id
     * @return 返回查找到的员工，否则返回null
     */
    public HeroNode postOrderSeek(int no) {
        HeroNode heroNode = null;
        if (this.left != null) {
            //左递归查找
            heroNode = this.left.postOrderSeek(no);
        }
        if (heroNode != null) {
            //在左子树上查找到
            return heroNode;
        }
        if (this.right != null) {
            //右递归
            heroNode = this.right.postOrderSeek(no);
        }
        //遍历当前节点
        if (no == this.id) {
            //找到直接返回
            return this;
        }
        return heroNode;
    }

    /**
     * 删除节点
     *
     * @param no 待删除节点id
     */
    public void deleteNode(int no) {
        if (this.left != null && this.left.getId() == no) {
            //左侧节点为待删除节点
            this.left = null;
            return;
        }
        if (this.right != null && this.right.getId() == no) {
            //右侧节点为待删除节点
            this.left = null;
            return;
        }
        //左右节点都不是待删除结点，则递归删除
        if (this.left != null) {
            //左递归
            this.left.deleteNode(no);
        }
        if (this.right != null) {
            //右递归
            this.right.deleteNode(no);
        }
    }
}